package 动态规划专项训练.动态规划训练2;

/**516. 最长回文子序列
 * @author zx
 * @create 2022-04-23 17:20
 */
public class Num516 {
    /**
     * @return 加入记忆化搜索
     */
    int[][] f = null;
    char[] ss = null;
    //记忆化搜索的好处：写起来简单,很直观

    public int longestPalindromeSubseq2(String s) {
        ss = s.toCharArray();
        int n = ss.length;
        if(n == 0){
            return 0;
        }
        f = new int[n][n];
        int i,j;
        for(i = 0;i < n;i++){
            for(j = i;j < n;j++){
                f[i][j] = -1;//还没有计算
            }
        }
        compute(0,n - 1);
        return f[0][n - 1];
    }
    //递归函数作用：计算f[i][j]
    private void compute(int i,int j){
        //记忆化搜索
        if(f[i][j] != -1){
            return;//如果已经计算了,直接返回
        }
        //递归终止条件是递推的初始问题
        if(i == j){
            f[i][j] = 1;
            return;
        }
        if(i + 1 == j){
            f[i][j] = (ss[i] == ss[j]) ? 2 : 1;
            return;
        }
        //第一次计算
        compute(i,j - 1);
        compute(i + 1,j);
        compute(i + 1,j - 1);
        f[i][j] = Math.max(f[i][j - 1],f[i + 1][j]);
        if(ss[i] == ss[j]){
            f[i][j] = Math.max(f[i][j],f[i + 1][j - 1] + 2);
        }
    }
    /**
     * @return 常规动态规划
     */
    public int longestPalindromeSubseq(String s) {
        char[] ss =s.toCharArray();
        int n = ss.length;
        if(n == 0){
            return 0;
        }
        int[][] f = new int[n][n];
        int i,j;
        //init
        //length 1
        for(i = 0;i < n;i++){
            f[i][i] = 1;
        }
        //length 2
        for(i = 0;i < n - 1;i++){
            f[i][i + 1] = (ss[i] == ss[i + 1]) ? 2 : 1;
        }
        int len;
        for(len = 3;len <= n;len++){
            //------------------ len ---------------
            // n - len  ----  n - 1
            //left：i,  right：j
            for(i = 0;i <= n - len;i++){
                j = i + len - 1;
                f[i][j] = Math.max(f[i][j - 1],f[i + 1][j]);
                if(ss[i] == ss[j]){
                    f[i][j] = Math.max(f[i][j],f[i + 1][j - 1] + 2);
                }
            }
        }
        return f[0][n - 1];
    }
}
